\select@language {spanish}
\contentsline {section}{\numberline {1}Introducci\'on}{4}
\contentsline {subsection}{\numberline {1.1}Aplicaciones en la vida real}{4}
\contentsline {section}{\numberline {2}Algoritmo Exacto}{5}
\contentsline {subsection}{\numberline {2.1}Enunciado}{5}
\contentsline {subsection}{\numberline {2.2}Desarrollo de la soluci\'on}{5}
\contentsline {subsubsection}{\numberline {2.2.1}Detalles de implementaci\'on}{5}
\contentsline {subsubsection}{\numberline {2.2.2}Algoritmo exacto}{6}
\contentsline {subsection}{\numberline {2.3}Pseudo-C\'odigo}{6}
\contentsline {subsection}{\numberline {2.4}C\'alculo de Complejidad}{6}
\contentsline {subsubsection}{\numberline {2.4.1}Tama\~no de entrada}{8}
\contentsline {subsection}{\numberline {2.5}Gr\'aficos de Complejidad}{10}
\contentsline {subsection}{\numberline {2.6}Conclusiones}{10}
\contentsline {subsection}{\numberline {2.7}Instrucciones de Uso}{10}
\contentsline {section}{\numberline {3}Heur\IeC {\'\i }stica Constructiva}{11}
\contentsline {subsection}{\numberline {3.1}Enunciado}{11}
\contentsline {subsection}{\numberline {3.2}Introducci\'on Algoritmos Golosos}{11}
\contentsline {subsection}{\numberline {3.3}Desarrollo de la soluci\'on}{11}
\contentsline {subsection}{\numberline {3.4}Pseudo-C\'odigo}{12}
\contentsline {subsection}{\numberline {3.5}C\'alculo de Complejidad}{13}
\contentsline {subsection}{\numberline {3.6}C\'alculo de Complejidad en Funci'on del Tama\~no de entrada}{15}
\contentsline {subsection}{\numberline {3.7}Casos Malos}{15}
\contentsline {subsection}{\numberline {3.8}Gr\'aficos de Complejidad}{16}
\contentsline {subsection}{\numberline {3.9}Conclusiones}{16}
\contentsline {subsection}{\numberline {3.10}Instrucciones de Uso}{16}
\contentsline {section}{\numberline {4}Heur\IeC {\'\i }stica Local}{17}
\contentsline {subsection}{\numberline {4.1}Introducci\'on Heur\IeC {\'\i }stica Local}{17}
\contentsline {subsection}{\numberline {4.2}Desarrollo de la soluci\'on}{17}
\contentsline {subsection}{\numberline {4.3}Pseudo-C\'odigo}{18}
\contentsline {subsection}{\numberline {4.4}C\'alculo de Complejidad}{19}
\contentsline {subsubsection}{\numberline {4.4.1}Tama\~no de entrada}{19}
\contentsline {subsection}{\numberline {4.5}Gr\'aficos de Complejidad}{20}
\contentsline {subsection}{\numberline {4.6}Pruebas}{21}
\contentsline {subsubsection}{\numberline {4.6.1}Mejora con respecto a una soluci\'on aleatoria}{21}
\contentsline {subsubsection}{\numberline {4.6.2}Soluci\'on Inicial - Random o golosa? }{21}
\contentsline {subsubsection}{\numberline {4.6.3}Comparaci\'on del Algoritmo Goloso con la heur\IeC {\'\i }stica de B\'usqueda local }{23}
\contentsline {subsection}{\numberline {4.7}Casos Malos}{24}
\contentsline {subsection}{\numberline {4.8}Conclusiones}{24}
\contentsline {section}{\numberline {5}Metaheur\IeC {\'\i }stica Grasp}{26}
\contentsline {subsection}{\numberline {5.1}Enunciado}{26}
\contentsline {subsection}{\numberline {5.2}Introducci\'on a Grasp}{26}
\contentsline {subsection}{\numberline {5.3}Desarrollo de la soluci\'on}{26}
\contentsline {subsection}{\numberline {5.4}Pseudo-C\'odigo}{27}
\contentsline {subsection}{\numberline {5.5}C\'alculo de Complejidad}{27}
\contentsline {subsubsection}{\numberline {5.5.1}Tama\~no de entrada}{27}
\contentsline {subsection}{\numberline {5.6}Gr\'aficos de Complejidad}{27}
\contentsline {subsection}{\numberline {5.7}Fijaci\'on de Par\'ametros}{27}
\contentsline {subsubsection}{\numberline {5.7.1}Cantidad de Iteraciones}{29}
\contentsline {subsubsection}{\numberline {5.7.2}Conclusiones}{31}
\contentsline {subsubsection}{\numberline {5.7.3}Lista restringida de candidatos (LRC)}{31}
\contentsline {subsection}{\numberline {5.8}Conclusiones}{31}
